class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int m = triangle.size();
        vector<vector<int>> dp(m);
        for(int i = 0; i < m; i++)
        {
            dp[i] = vector<int>(triangle[i].size());
            if(i == 0)
                dp[i][0] = triangle[i][0];
            else
                dp[i][0] = triangle[i][0] + dp[i-1][0];
        }

        for(int i = 1; i < m; i++)
        {
            int n = triangle[i].size();
            for(int j = 1; j < n; j++)
            {
                if(j == n-1)
                    dp[i][j] = dp[i-1][j-1] + triangle[i][j];
                else
                    dp[i][j] = min(dp[i-1][j-1],dp[i-1][j]) + triangle[i][j];
            }
        }

        int res = INT_MAX;
        for(int i = 0; i < dp[m-1].size(); i++)
        {
            res = min(dp[m-1][i], res);
        }

        return res;
    }
};